package com.czk.tree.threaded;

import lombok.Getter;
import lombok.Setter;

/**
 * 前、中、后序线索化的实现
 * @Author:ChenZhangKun
 * @Date: 2020/7/7 21:27
 */
public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        // 创建二叉树
        Node node4 = new Node(4, null, null);
        Node node5 = new Node(5, null, null);
        Node node2 = new Node(2, node4, node5);
        Node node6 = new Node(6, null, null);
        Node node7 = new Node(7, null, null);
        Node node3 = new Node(3, node6, node7);
        Node node1 = new Node(1, node2, node3);
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.setNode(node1);
/*        // 中序线索化
        binaryTree.inOrderThreadedNode();
        // 5号节点的前驱结点
        System.out.println(node5.getLeft());// 2
        // 5好节点的后继节点
        System.out.println(node5.getRight());// 1*/

/*        System.out.println("前序遍历线索化");
        binaryTree.preThreadedNode();
        // 5号节点的前驱结点
        System.out.println(node5.getLeft());// 2
        // 5好节点的后继节点
        System.out.println(node5.getRight());// 1
        System.out.println("=====线索化遍历");
        binaryTree.threadedTraverse();*/
        System.out.println("后续线索化");
        binaryTree.postThreadedNode();
        // 5号节点的前驱结点
        System.out.println(node6.getLeft());// 2
        // 5好节点的后继节点
        System.out.println(node6.getRight());// 1
    }
}
// 线索化二叉树的定义

class BinaryTree {
    private Node node;

    public void setNode(Node node) {
        this.node = node;
    }

    // 遍历线索化二叉树
    public void threadedTraverse(){
        Node node=this.node;
        while (node!=null){
            // 没有空余指针的默认为0
            while (node.getLeftType()==0){
                node=node.getLeft();
            }
            System.out.print(node+"  ");
            // 设置了指针，此时指向了节点
            while (node.getRightType()==1){
                node=node.getRight();
                System.out.print(node+" ");
            }
            // 替换遍历的节点
            node=node.getRight();
        }
    }
    // 方法的重载
    public void postThreadedNode(){
        this.postThreadedNode(node);
    }
    // 后续遍历线索化二叉树
    public void postThreadedNode(Node node){
        if (node==null) return;

        // 线索化左子树

            postThreadedNode(node.getLeft());


        // 线索化右子树

            postThreadedNode(node.getRight());

        // 先进行处理
        // 线索化当前节点
        // 先处理当前节点的前序节点
        if (node.getLeft()==null){
            // 当前节点的左指针指向前驱节点
            node.setLeft(pre);
            // 设置指针类型
            node.setLeftType(1);
        }
        // 处理右指针
        if (pre!=null&&pre.getRight()==null){
            // 让前驱节点的右指针指向当前节点
            pre.setRight(node);
            // 设定类型
            pre.setRightType(1);
        }
        // 每次处理一个节点，让当前节点变为前驱节点
        pre=node;
    }


    // 方法的重载
    public void preThreadedNode(){
        this.preThreadedNode(this.node);
    }
    // 前序线索化二叉树
    public void preThreadedNode(Node node){
        if (node==null) return;
        // 先进行处理
        // 线索化当前节点
        // 先处理当前节点的前序节点
        if (node.getLeft()==null){
            // 当前节点的左指针指向前驱节点
            node.setLeft(pre);
            // 设置指针类型
            node.setLeftType(1);
        }
        // 处理右指针
        if (pre!=null&&pre.getRight()==null){
            // 让前驱节点的右指针指向当前节点
            pre.setRight(node);
            // 设定类型
            pre.setRightType(1);
        }
        // 每次处理一个节点，让当前节点变为前驱节点
        pre=node;
        // 线索化左子树
        if (node.getLeftType()==0){
            preThreadedNode(node.getLeft());
        }

        // 线索化右子树
        if (node.getRightType()==0){
            preThreadedNode(node.getRight());
        }

    }


    public void inOrderThreadedNode(){
        this.inOrderThreadedNode(this.node);
    }
    // 预留保持前一个节点的数据
    private Node pre=null;
    // 中序线索化节点方法
    // node当前需要线索化的节点
    public void inOrderThreadedNode(Node node){
        // 判断
        if (node==null){
            return;
        }
        // 进行中序线索化处理
        // 先线索化左子树
        inOrderThreadedNode(node.getLeft());
        // 线索化当前节点
        // 先处理当前节点的前序节点
        if (node.getLeft()==null){
            // 当前节点的左指针指向前驱节点
            node.setLeft(pre);
            // 设置指针类型
            node.setLeftType(1);
        }
        // 处理右指针
        if (pre!=null&&pre.getRight()==null){
            // 让前驱节点的右指针指向当前节点
            pre.setRight(node);
            // 设定类型
            pre.setRightType(1);
        }
        // 每次处理一个节点，让当前节点变为前驱节点
        pre=node;
        // 线索化右子树
        inOrderThreadedNode(node.getRight());

    }



    // 删除节点
    public void delete(int name){
        if (node!=null){
            if (node.getName()==name){
                node=null;
            }else {
                node.delete(name);
            }
        }else {
            System.out.println("主节点为空");
            return;
        }
    }
    // 前序遍历
    public void preTraverse() {
        if (node != null) {
            node.preTraverse();
        }
    }

    // 中序遍历
    public void inOrderTraverse() {
        if (node != null) {
            node.inOrderTraverse();
        }
    }

    // 后续遍历
    public void postTraverse() {
        if (node != null) {
            node.postTraverse();
        }
    }
    // 前序查找
    public Node getByPreTraverse(int name){
        return node.getByPreTraverse(name);
    }
    // 中序查找
    public Node getByPostTraverse(int name){
        return node.getByPostTraverse(name);
    }
    // 前序查找
    public Node getByInOrderTraverse(int name){
        return node.getByInOrderTraverse(name);
    }
}
// 创建节点对象
@Getter
@Setter
class Node {
    // 名字
    private Integer name;
    // 左节点
    private Node left;
    // 右节点
    private Node right;
    // 左指针索引类型 0 左子树，1 前驱结点
    private Integer leftType=0;
    // 右指针索引类型 0 右子树，1 后继结点
    private Integer rightType=0;
    public Node(Integer name, Node left, Node right) {
        this.name = name;
        this.left = left;
        this.right = right;
    }

    /**
     * 删除节点
     * 使用递归操作
     * @param name
     */
    public void delete(int name){
        // 左子节点是否要删除
        if (this.getLeft()!=null&&this.getLeft().getName()==name){
            // 置为空
            this.setLeft(null);
            return;
        }
        // 右子节点删除
        if (this.getRight()!=null&&this.getRight().getName()==name){
            // 值为空
            this.setRight(null);
            return;

        }
        // 向左子树递归
        if (this.getLeft()!=null){
            this.getLeft().delete(name);
        }
        // 向右子树递归
        if (this.getRight()!=null){
            this.getRight().delete(name);
        }

    }
    @Override
    public String toString() {
        return  name+"";
    }

    // 先续遍历
    public void preTraverse() {

        System.out.print(this + " ");
        if (this.getLeft() != null) {
            this.getLeft().preTraverse();
        }
        if (this.getRight() != null) {
            this.getRight().preTraverse();

        }

    }

    // 中序遍历
    public void inOrderTraverse() {
        if (this.getLeft() != null) {
            this.getLeft().inOrderTraverse();
        }
        System.out.print(this + " ");
        if (this.getRight() != null) {
            this.getRight().inOrderTraverse();
        }
    }

    // 后续遍历
    public void postTraverse() {
        if (this.getLeft() != null) {
            this.getLeft().postTraverse();
        }
        if (this.getRight() != null) {
            this.getRight().postTraverse();
        }
        System.out.print(this + " ");
    }
    // 前序遍历查找
    public Node getByPreTraverse(int name){
        // 先与当前节点比较，找到则返回
        System.out.println("进入前序查找");
        if (this.getName()==name){
            return this;
        }
        // 定义变量接收数据
        Node result=null;
        // 向左递归
        if (this.getLeft()!=null){
            result=this.getLeft().getByPreTraverse(name);
        }
        // 不等于空则返回结果
        if (result!=null){
            return result;
        }
        // 向右递归
        if (this.getRight()!=null){
            result=this.getRight().getByPreTraverse(name);
        }
        // 返回结果
        if (result!=null){
            return result;
        }
        return null;
    }
    // 中序查找
    public Node getByInOrderTraverse(int name){
        Node result=null;
        // 先左递归
        if (this.getLeft()!=null){
            result=this.getLeft().getByInOrderTraverse(name);
        }
        // 与当前节点比较
        if (result!=null){
            return result;
        }
        System.out.println("进入中序查找");
        if (this.getName()==name){
            return this;
        }
        // 后续递归
        if (this.getRight()!=null){
            result=this.getRight().getByInOrderTraverse(name);
        }
        return result;
    }
    // 后续递归查找
    public Node getByPostTraverse(int name){
        // 左递归
        Node result=null;
        if (this.getLeft()!=null){
            result=this.getLeft().getByPostTraverse(name);
        }
        if (result!=null){
            return result;
        }
        // 右递归
        if (this.getRight()!=null){
            result=this.getRight().getByPostTraverse(name);
        }
        if (result!=null){
            return result;
        }
        System.out.println("进入后续查找");
        // 与当前节点比较
        if (this.getName()==name){
            return this;
        }
        return null;
    }
}
